package com.gxc.recursion;

/**
 * 现有n1 arr1[] + n2 arr2[] 种面值的硬币，其中前n1种为普通币，可以取任意枚，
 * 后n2种为纪念币每种最多只能取一枚，每种硬币有一个面值，
 * 问能用多少种方法拼出m的面值?
 *
 * 解法：
 * arr1
 * 循环尝试 ，arr1[0] 从i枚 ，尝试到最大 m/arr1[0], 剩余的金币  m - arr1[0] * i,
 * 继续 arr1[1] 从i枚 尝试
 *
 * arr2
 * 一个map记录尝试不同组合能够构成的面值
 */
public class Money {

    public static void main(String[] args) {
        int[] arr1 = new int[]{87, 76, 15, 79, 53};
        int[] arr2 = new int[]{1, 94, 59, 30, 5};
        int target = 100;

        System.out.println(process(arr1, arr2, target));
        System.out.println(process2(arr1, arr2, target));

        System.out.println("-------------");
        System.out.println(attempt2(arr2, 0, 100));
    }

    public static int process(int[] arr1, int[] arr2, int target) {
        int[][] many = dp1_1(arr1, target);
        int[][] one = dp2_1(arr2, target);

        int sum = 0;
        for (int i = 0; i <= target; i++) {
            sum += many[0][i] * one[0][target-i];
        }
        return sum;
    }

    public static int process2(int[] arr1, int[] arr2, int target) {
        int[][] many = dp1_1(arr1, target);
        int[][] one = dp2(arr2, target);

        int sum = 0;
        for (int i = 0; i <= target; i++) {
            sum += many[0][i] * one[arr2.length-1][target-i];
        }
        return sum;
    }

    /**
     * 普通币，可以取任意枚,能用多少种方法拼出m的面值
     * @param arr1
     * @param i
     * @param remaining
     * @return
     */
    public static int attempt1(int[] arr1, int i, int remaining) {
        if (remaining == 0) return 1;
        if (remaining < 0 || i == arr1.length-1) return 0;

        int sum = 0;
        int max = remaining/arr1[i];
        for (int j = 0; j <= max; j++) {
            sum +=  attempt1(arr1, i+1, remaining - arr1[i]*j);
        }
        return sum;
    }

    public static int[][] dp1_1(int[] arr1, int target) {
        int[][] dp = new int[arr1.length][target+1];

        //硬币 i 任取，拼出 0 ，只有都不取一种方式
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = arr1.length-2; i >= 0; i--) {
            for (int j = 1; j <= target; j++) {
                int max = j/arr1[i];
                for (int num = 0; num <= max; num++) {
                    //dp[i][j] +=  dp[i+1][j - arr1[i]*num];

                    //可以记忆搜索
                    //可以斜率优化 dp[i][j] += dp[i+1][j - arr1[i]*num] ;
                    // dp[i][j-arr1[i]] +=   dp[i+1][j - arr1[i]* num - arr1[i]*num] ;
                    // 所以 dp[i][j] =  dp[i][j - arr1[i]] + dp[i+1][j] ;
                    dp[i][j] =  dp[i+1][j] + (j-arr1[i]>=0?dp[i][j - arr1[i]]:0);
                }
            }
        }

        return dp;
    }

    /**
     * 纪念币每种最多只能取一枚，每种硬币有一个面值,能用多少种方法拼出m的面值
     * @param arr2  纪念币硬币
     * @param i     当前硬币
     * @param remaining     剩余
     * @return
     */
    public static int attempt2(int arr2[], int i, int remaining) {
        if (remaining == 0) return 1;
        if (remaining < 0 || i == arr2.length) return 0;

        int take = attempt2(arr2, i+1, remaining - arr2[i]);
        int notTake = attempt2(arr2, i+1, remaining);

        return take+notTake;
    }

    /**
     * 纪念币每种最多只能取一枚，每种硬币有一个面值,能用多少种方法拼出m的面值
     * @param arr2
     * @param target
     * @return
     */
    public static int[][] dp2(int arr2[], int target) {
        int dp[][] = new int[arr2.length][target+1];

        //纪念币 i 任取，拼出 0 ，只有都不取一种方式
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        //纪念币 0 取，拼出 j ，只有 j = arr2[0]的情况
        if (arr2[0] <= target) dp[0][arr2[0]] = 1;

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                //当前硬币i 组合成 j 的方法数 = 硬币  i-1 可以组合成 j 的方法数 + （硬币  i-1 可以组合成 j-arr[i]（当前硬币面值） 的方法数）
                dp[i][j] = dp[i-1][j];
                if (j-arr2[i]>=0) {
                    dp[i][j] += dp[i-1][j-arr2[i]];
                }
            }
        }
        return dp;
    }

    /**
     * 根据递归推dp
     * @param arr2
     * @param target
     * @return
     */
    public static int[][] dp2_1(int arr2[], int target) {
        int dp[][] = new int[arr2.length+1][target+1];

        //纪念币 i 任取，拼出 0 ，只有都不取一种方式
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = arr2.length-1; i >= 0; i--) {
            for (int j = 1; j <= target; j++) {
                //当前硬币i 组合成 j 的方法数 = 硬币  i-1 可以组合成 j 的方法数 + （硬币  i-1 可以组合成 j-arr[i]（当前硬币面值） 的方法数）
                dp[i][j] = dp[i+1][j];
                if (j-arr2[i]>=0) {
                    dp[i][j] += dp[i+1][j-arr2[i]];
                }
            }
        }
        return dp;
    }

}
